Merkle Tree
https://scrapbox.io/files/643a3b52a1c9a2001c8982a7.png
別に二分木である必要はない
それはそうkekeho.icon
全てのノードはサブMerkle Treeのルート
$ log_2(n)で,与えられたデータがMerkle Treeに含まれるか検証できる($ nはLeafの数)
最低限の各節のハッシュ値も知っている必要がある
自己検証ができる
同じ葉を持つTreeの根は、同じハッシュ値になる
データの重複排除に使える
活用例
同期の最適化(同じ葉を持つTreeの根が同じハッシュ値になる性質を活かす)
ブロックチェーン
解説記事
実装例
code:rust
use ring::digest::{Digest, SHA256, Context};
use std::rc::Rc;
struct Node {
hash: Digest,
left: Option<Rc<Node>>,
right: Option<Rc<Node>>,
}
fn digest(data: &u8) -> Digest { let mut context = Context::new(&SHA256);
context.update(data);
let digest = context.finish();
return digest;
}
fn add(left: &Digest, right: &Digest) -> Digest {
let or: Vec<u8> = left.as_ref().iter().zip(right.as_ref().iter()).map(|(&l, &r)| l | r).collect();
}
impl Node {
pub fn include(self: &Rc<Node>, data: &u8, digests: &&Digest) -> bool { let mut prev_hash = digest(data);
for digest in digests {
prev_hash = add(&prev_hash, digest);
}
if self.hash.as_ref() == prev_hash.as_ref() {
return true
}
return false;
}
pub fn merge(left: Rc<Node>, right: Rc<Node>) -> Rc<Node> {
let parent: Rc<Node> = Rc::new(Node {
hash: add(&left.hash, &right.hash),
left: Some(left),
right: Some(right),
});
return parent;
}
fn build_nodetree(nodes: &Rc<Node>) -> Rc<Node> { if nodes.len() == 1 {
}
let mut parent_list: Vec<Rc<Node>> = Vec::new();
for i in (0..nodes.len()).step_by(2) {
if nodes.len() == i+1 {
// 奇数この場合、最後の要素を複製する
parent_list.push(parent);
break;
}
let parent = Node::merge(nodesi.clone(), nodesi+1.clone()); parent_list.push(parent);
}
return Node::build_nodetree(&parent_list)
}
pub fn build_tree(data: &[&u8]) -> Rc<Node> { let mut leaf_list: Vec<Rc<Node>> = Vec::new();
for v in data {
let d = digest(v);
leaf_list.push(
Rc::new(Node {
hash: d,
left: None,
right: None,
})
);
}
return Node::build_nodetree(&leaf_list..) }
}
fn main() {
let datalist = [
"hoge",
"fuga",
"piyo",
].map(|d| d.as_bytes());
// Build Merkle Tree
let root = Node::build_tree(&datalist..); // Check piyo!
let data = "piyo";
let given_digests = [
&root.right.clone().unwrap().left.clone().unwrap().hash,
&root.left.clone().unwrap().hash
];
if root.include(data.as_bytes(), &given_digests) {
println!("{} include!", data);
} else {
println!("error");
}
// Check fuga!
let data = "fuga";
let given_digests = [
&root.left.clone().unwrap().left.clone().unwrap().hash,
&root.right.clone().unwrap().hash
];
if root.include(data.as_bytes(), &given_digests) {
println!("{} include!", data);
} else {
println!("error");
}
// Wrong digests
let data = "fuga";
let given_digests = [
&root.left.clone().unwrap().left.clone().unwrap().hash,
&root.left.clone().unwrap().hash
];
if root.include(data.as_bytes(), &given_digests) {
println!("error");
} else {
println!("wrong digests");
}
// Check not include
let data = "unko";
let given_digests = [
&root.left.clone().unwrap().right.clone().unwrap().hash,
&root.right.clone().unwrap().hash
];
if root.include(data.as_bytes(), &given_digests) {
println!("error")
} else {
println!("{} is not included", data);
}
}